#include <stdio.h>
#include <cstdlib>

typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化单链表（带头结点）
bool InitList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode)); // 创建头结点
    if (L == NULL)
    { // 内存分配失败
        return false;
    }
    L->next = NULL; // 头结点指针置空
    return true;
}

// 销毁单链表
void DestroyList(LinkList &L)
{
    LNode *p = L; // 指向当前结点
    while (p != NULL)
    { // 遍历链表
        LNode *temp = p;
        p = p->next; // 移动到下一结点
        free(temp);  // 释放当前结点
    }
    L = NULL; // 头指针置空
}

// 在位置i插入元素e
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)
        return false; // 非法位置

    LNode *p = L; // 指向头结点
    int j = 0;    // 当前遍历位置

    // 寻找第i-1个结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
        return false; // i值不合法

    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false; // 内存分配失败

    s->data = e;       // 存储数据
    s->next = p->next; // 新结点指向原后继
    p->next = s;       // 原前驱指向新结点
    return true;
}

// 删除位置i的元素，通过e返回
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1)
        return false; // 非法位置

    LNode *p = L; // 指向头结点
    int j = 0;    // 当前遍历位置

    // 寻找第i-1个结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    // 检查删除位置有效性
    if (p == NULL || p->next == NULL)
    {
        return false;
    }

    LNode *q = p->next; // 指向待删除结点
    e = q->data;        // 获取删除值
    p->next = q->next;  // 绕过待删除结点
    free(q);            // 释放内存
    return true;
}

// 查找元素e的位置（从1开始）
int LocateElem(LinkList L, int e)
{
    LNode *p = L->next; // 指向第一个数据结点
    int pos = 1;        // 当前位置

    while (p != NULL)
    {
        if (p->data == e)
        {
            return pos; // 找到返回位置
        }
        p = p->next;
        pos++;
    }
    return 0; // 未找到
}

// 获取位置i的元素值
int GetElem(LinkList L, int i)
{
    if (i < 1)
        return NULL; // 非法位置

    LNode *p = L->next; // 指向第一个数据结点
    int j = 1;          // 当前遍历位置

    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    return (p != NULL) ? p->data : NULL;
}

// 打印链表内容
void PrintList(LinkList L)
{
    LNode *p = L->next; // 跳过头结点
    printf("List: [");
    while (p != NULL)
    {
        printf("%d", p->data);
        if (p->next != NULL)
            printf("->");
        p = p->next;
    }
    printf("]\n");
}

// 检查链表是否为空
bool Empty(LinkList L)
{
    return (L->next == NULL);
}

int main()
{
    LinkList L;
    InitList(L); // 初始化

    // 插入元素
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 3, 30);

    PrintList(L); // List: [10->20->30]

    // 删除元素
    int deleted;
    ListDelete(L, 2, deleted);
    printf("Deleted: %d\n", deleted); // Deleted: 20

    // 按值查找
    int pos = LocateElem(L, 30);
    printf("Position: %d\n", pos); // Position: 2

    // 按位查找
    int val = GetElem(L, 1);
    printf("Value: %d\n", val); // Value: 10

    DestroyList(L); // 销毁链表
    return 0;
}